package com.ma.graph;

import java.util.LinkedList;
import java.util.List;

/*

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

    public List<List<Integer>> allPathsSourceTarget(int[][] graph)

* */
public class Solution797 {

    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        LinkedList<Integer> path = new LinkedList<>();
        int n = graph.length;
        traverse(graph, 0, path , n);
        return res;
    }

    private void traverse(int[][] graph, int s, LinkedList<Integer> path , int n) {
        path.addLast(s);
        if (s == n - 1) {
            res.add(new LinkedList<>(path));
            path.removeLast();
            return;
        }
        for(int v:graph[s]){
            traverse(graph, v, path , n);
        }
        path.removeLast();


    }

    public static void main(String[] args) {
        //graph = [[1,2],[3],[3],[]]
        int[][] graph = {{1,2},{3},{3},{}};
        Solution797 solu = new Solution797();
        List<List<Integer>> lists = solu.allPathsSourceTarget(graph);
        System.out.println(lists);
        
        int[] a = {1,2,3,4};
        for (int i : a) {
            System.out.println(i);
        }
    }


}
